Modern computer graphics often rely on the use of modeled objects. Such objects are often modeled using polygons. Conveniently, objects so modeled may easily be rotated, scaled, and otherwise manipulated.
As a consequence, the formation of a suitable polygons to represent an object, often referred to as polygonization, is becoming of great significance in the field of computer graphics. An object is typically polygonized by forming a mesh of interconnected polygons from a collection of points in three space recovered from one or more images depicting the object.
Example uses of polygonized objects, include three dimensional (“3D”) games, virtual reality games, and multimedia applications. In such applications 3D objects and scenes are typically represented as meshes so that graphics acceleration hardware can be utilized to generate high quality images of the objects and scenes. Furthermore, most of conventional animation techniques, are best processed using polygonized representations of objects.
Similarly, in the manufacturing industry, almost all computer-aided design, engineering, and manufacturing (CAD/CAE/CAM) software use 3D meshes for finite element analysis, assembly planning, process automation, and manufacturing using numerical control.
Likewise, the inclusion of 3D objects using mark-up languages for presentation on Internet web pages is becoming a trend. In many Internet standards for presenting 3D content, e.g., VRML2, MPEG-4, and Java3D, polygonized objects are of increasing significance.
Even though polygonization has been actively studied for about ten years, many challenges still exist. For example, many known algorithms only work for objects that do not have holes, and cannot handle shapes such as torroids and the like, for example. Examples of these algorithms include approaches using deformable models. Similarly, many known algorithms cannot reliably locate shape boundaries—shape boundaries are usually smoothed out. Yet other known algorithms produce meshes with holes caused by the non-uniform sampling of 3D points. Moreover, the presence of noise can severely deteriorate the polygonization results.
Abstractly, polygonization methods seek to construct a polygon mesh, possibly with boundary, from sampled points in 3D space without any additional information about the structure or organization of points (see for example H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. “Surface reconstruction from unorganized points.” In Proc. SIGGRAPH '92, pages 71–78, 1992). A more complete approach further constrains the sampled 3D points by additional features present in the images from which the points are sampled. (see, for example N. Amenta, M. Bern, and M. Kamvysselis. “A new Voronoi-based surface reconstruction algorithm.” In Proc. SIGGRAPH '98, pages 415–421, 1998 ).
Example known polygonization algorithms include the zero-set algorithm as detailed in B. Curless and M. Levoy. “A volumetric method for building complex models from range images.” In Proc. SIGGRAPH '96, pages 303–312, 1996 and H. Hoppe, T. DeRose, T. Duchamp, J. McDonald, and W. Stuetzle. “Surface reconstruction from unorganized points.” In Proc. SIGGRAPH '92, pages 71–78, 1992; “crust algorithms” and “alpha shape algorithms” detailed in H. Edelsbrunner, D. G. Kirkpatrick, and R. Seidel. “On the shape of a set of points in the plane.” IEEE Trans. on Information Theory, 29:551–559, 1983, and H. Edelsbrunner and E. P. Mucke. “Three-dimensional alpha shapes.” ACM TOG, 13:43–72, 1994;
The zero-set algorithms are based on a volumetric framework. A signed distance function in three space is defined from the input points and their zero-sets are computed as the output mesh. These algorithms, however, produce approximating meshes (i.e. ones that approximate sampled points) instead of interpolating meshes (i.e. ones that are formed from, and contain the sampled points).
The alpha-shape and crust algorithms make use of Voronoi diagrams and Delaunay triangulation to construct triangle mesh. A Voronoi diagram for an arbitrary set of points may be formed from convex polygons created from the perpendicular bisector of lines between nearest neighboring points. Delaunay triangulation forms a mesh using the Voronoi diagrams.
The alpha-shape algorithms use a simplex (edge, triangle, or tetrahedron) in an alpha-shape if it contains some circumspheres with no interior sample points. A 3D circumsphere is a sphere of radius alpha whose surface touches at least three sample points. The alpha-shapes for all possible values of alpha approximate the overall shape and natural dimensionality of a set of sampled points. Alpha-shape algorithms cannot readily be applied to non-uniformly distributed sets of 3D points. Similarly, non-uniformly distributed sets of 3D points cannot be easily clustered into clusters having a fixed sampling density for assigning a fixed alpha.
The crust algorithm uses three-dimensional Voronoi diagram with provable guarantees. Advantageously, the output is guaranteed to be topologically correct and convergent to the original surface as the sampling density increases for a “good sample” from a smooth surface. A “good sample” has a sampling density that varies locally so as to rigorously capture the intuitive notion that featureless areas can be reconstructed from fewer samples. Unfortunately, collecting such a “good sample” is difficult for 3D points recovered from arbitrary images. Moreover, the crust algorithm does not process surface discontinuities well.
Accordingly, there is a need for improved methods of polygonization, that may be used to polygonize arbitrary shapes including surface discontinuities.